package sort;

import java.util.Arrays;

/**
 * QuickSort
 *
 * @author admin
 * @version 2023/11/02 10:48
 **/
public class QuickSort implements SortStrategy{
    @Override
    public void sort(int[] a) {
        dfs(0,a.length-1,a);
    }
    public void dfs(int i,int j,int[] a)
    {
        if(i>j) return;
        int left=i;
        int right=j;
        int target=a[i];
        while(left<right)
        {
            while(left<right&&a[right]>target)
            {
                right--;
            }
            while(left<right&&a[left]<=target)
            {
                left++;
            }
            swap(left,right,a);
        }
        swap(right,i,a);
        dfs(i,right-1,a);
        dfs(right+1,j,a);
    }

}
